# coding: utf-8
'''
Created on 22/06/2013

@author: Vagner Clementino
'''
import inverse_module_n
        
def new_xab(tupla_xab, P, alpha, beta):
    '''
        Calcula os valores de x, a e b conforme descrito, respectivamente,
        nas equações 3.2, 3.3 e 3.4 do HAC
    '''
    new_xab = ()
    partition = tupla_xab[0] % 3
    
    if (partition == 0):
        temp_x = (tupla_xab[0] * tupla_xab[0]) % P 
        temp_a = (2 * tupla_xab[1]) % (P - 1)
        temp_b = (2 * tupla_xab[2]) % (P - 1)
    elif (partition == 1):
        temp_x = (tupla_xab[0] * alpha) % P 
        temp_a = (tupla_xab[1] + 1) % (P - 1)
        temp_b = tupla_xab[2]
    elif (partition == 2):
        temp_x = (tupla_xab[0] * beta) % P 
        temp_a = tupla_xab[1]
        temp_b = (tupla_xab[2] + 1) % (P - 1)
        
    new_xab = (temp_x, temp_a, temp_b)
        
    return new_xab
        
     
def pollard_rho(P, alpha, beta):    
    '''
        Retorna o logaritmo discreto x de grupo multiplicativo modulo P, onde
        P é primo,
        dado o generator (lemento primitivo de grupo multiplicativo módulo P)
     '''
    
    x = 1
    a = 0
    b = 0
    X = x
    A = a
    B = b
    tupla_xab = (x, a, b)
    aux_tupla_xab = (X, A, B)
    i = long(1)
    
    while i < (P - 1):
        tupla_xab = new_xab(tupla_xab, P, alpha, beta)
        aux_tupla_xab = new_xab(aux_tupla_xab, P, alpha, beta)
        aux_tupla_xab = new_xab(aux_tupla_xab, P, alpha, beta)
        
        # print("{} {} {} ".format(i, tupla_xab, aux_tupla_xab))
        
        if(tupla_xab [ 0 ] == aux_tupla_xab [0]):
            r = (tupla_xab[2] - aux_tupla_xab[2]) % (P-1) 
            if r == 0:
                return None
            else:
             inverse = inverse_module_n.inverse_mod_n(r, P-1)
             if inverse == None:
                 return None
             else:
                 discrete_log = inverse * (aux_tupla_xab[1] - tupla_xab[1]) % (P-1)
                 return discrete_log
        else:
            i += 1